package demo.letcode.top100;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * todo
 * <p>
 * 请根据每日气温列表，重新生成一个列表。
 * 对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温再这之后都不会升高
 * 请在该位置用0代替
 * 例如:给定一个列表temperatures=[73,74,75,71,69,72,76,73]
 * 输出[1,1,4,2,1,1,0,0]
 *
 * @author taqo
 * @date 2021/5/7
 */
public class _每日温度2 {
    public static void main(String[] args) {
        int a[] = {73, 74, 75, 71, 69, 72, 76, 73};
        int len = a.length;
        // 寻找最近比当前大的一个位置
        int[] dp = new int[len];
        // 向右入栈 一直找到比i大的
        // 如果idx比当前i大，则dp[i] = a[idx-i] 弹出当前i
        // 先找到比当前元素小的dp[idx]
        Deque<Integer> deque = new ArrayDeque<>();
        // 73, 74, 75, 71, 69, 72, 76, 73
        // 0   1   2   3   4   5   6   7
        // 1   2   6   5   5   6   0   0 // 比当前大的索引
        // 1   1   4   2   1   1   0   0 // 距离大的最近的距离
        // 找到其右侧第一个比它小的元素的下标
        for (int i = len-1; i >= 0; i--) {
            while (!deque.isEmpty() && a[i] > a[deque.peek()]) {
                // 弹出栈顶所有大于等于当前元素的下标
                deque.pop();
            }
            if (!deque.isEmpty()) {
                // 说明栈顶就是当前元素右侧第一个比它小的元素的下标
//                dp[i] = deque.peek();
                // 比当前i大的距离
                dp[i] = deque.peek()-i;
            }
            deque.push(i);
        }
        System.out.println(Arrays.toString(dp));

    }
}
